"""
    假设农场中的母牛每年会产生一头小母牛，并且永远不会死。第一年农场中只有一头成熟的母牛，第二年开始，母牛开始生小母牛，每只小母牛三年之后成熟又可以生小母牛，给定整数N，求N年后母牛的数量。
    1  
    2   
    3
    4
    6
    9
    # 我们考虑， 
        第 n 年 是不是 n - 3 年前的猪都成熟了
        所以
        f(n) = f(n-1) + f(n-3)
"""

# 解法一：

def getCount1(n):
    if n == 1 or n == 2 or n == 3:
        return n
    return getCount1(n-1) + getCount1(n-3) 

result = getCount1(5)
print(result)

#解法二： 动态规划
def getCount2(n):
    a = [0, 1, 2, 3]
    if n == 1 or n == 2 or n == 3:
        return a[n]
    for i in range(4, n+1):
        a.append(a[i-1] + a[i-3])
    return a[n]

result2 = getCount2(20)
print(result2)

